package com.yanceysong.codetop.s81_s90;

import com.yanceysong.common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * S83_Mid_662_二叉树最大宽度
 * <p>
 * https://leetcode.cn/problems/maximum-width-of-binary-tree/
 * <p>
 * 给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
 * <p>
 * 树的 最大宽度 是所有层中最大的 宽度 。
 * <p>
 * 每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
 */
public class S83_Mid_662_二叉树最大宽度 {
    private int ans;
    private Map<Integer, Integer> map;

    public int widthOfBinaryTree(TreeNode root) {
        ans = 0;
        map = new HashMap<>();
        dfs(root, 0, 0);
        return ans;
    }

    private void dfs(TreeNode root, int depth, int pos) {
        if (root == null) {
            return;
        }
        map.computeIfAbsent(depth, k -> pos);
        ans = Math.max(ans, pos - map.get(depth) + 1);
        dfs(root.left, depth + 1, pos * 2);
        dfs(root.right, depth + 1, pos * 2 + 1);
    }
}

